public class BinarySearchTree {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode root;
    //添加
    public boolean insert(int key){
        if(root==null){
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        //找到叶子节点
        while(cur!=null){
            if(cur.val<key){
                prev = cur;
                cur = cur.right;
            }else if(cur.val>key){
                prev = cur;
                cur = cur.left;
            }else{
                return false;
            }
        }
        TreeNode newnode = new TreeNode(key);
        if(prev.val>newnode.val){
            prev.left = newnode;
        }else{
            prev.right = newnode;
        }
        return true;
    }
    //中序遍历
    public void inorder(TreeNode root){
        if(root==null){
            return ;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    //查找
    public TreeNode search(int key){
        TreeNode cur = root;
        while(cur!=null){
            if(cur.val==key){
                return cur;
            }else if(cur.val>key){
                cur = cur.left;
            }else if(cur.val<key){
                cur = cur.right;
            }
        }
        return null;
    }
    public TreeNode remove(TreeNode root,int val){
        if(root==null){
            return null;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null){
            if(cur.val<val){
                prev = cur;
                cur = cur.right;
            }else if(cur.val>val){
                prev = cur;
                cur = cur.left;
            }else{
                removeNode(cur,prev,root);
                return root;
            }
        }
        return root;
    }
    private TreeNode removeNode(TreeNode cur,TreeNode prev,TreeNode root){
        if(cur.left==null || cur.right==null){
            if(cur.left==null){
                if(cur==root){
                    root = cur.right;
                }else if(prev.left==cur){
                    prev.left = cur.right;
                }else if(prev.right==cur){
                    prev.right = cur.right;
                }
            }else if(cur.right==null){
                if(cur==root){
                    root = cur.left;
                }else if(prev.left==cur){
                    prev.left = cur.left;
                }else if(prev.right==cur){
                    prev.right = cur.left;
                }
            }
        }else{
            TreeNode target = cur.right;
            TreeNode targetPrev = cur;
            while(target.left!=null){
                targetPrev = target;
                target = target.left;
            }
            cur.val = target.val;
            if(targetPrev.left==target){
                targetPrev.left = target.right;
            }else if(targetPrev.right==target){
                targetPrev.right = target.right;
            }
        }
        return root;
    }

//    public boolean remove(int key){
//        TreeNode cur = root;
//        TreeNode prev = null;
//        while(cur!=null){
//            if(cur.val<key){
//                prev = cur;
//                cur = cur.right;
//            } else if(cur.val>key){
//                prev = cur;
//                cur = cur.left;
//            }else{
//                removrNode(prev,cur);
//                return true;
//            }
//        }
//        return false;
//    }
//    private void removrNode(TreeNode prev,TreeNode cur){
//        if(cur.left==null){
//            if(cur==root){
//                root = cur.right;
//            }else if(prev.left==cur){
//                prev.left = cur.right;
//            }else if(prev.right==cur){
//                prev.right = cur.right;
//            }
//        }else if(cur.right==null){
//            if(cur==root){
//                root = cur.left;
//            }else if(prev.left==cur){
//                prev.left = cur.left;
//            }else if(prev.right==cur){
//                prev.right = cur.left;
//            }
//        }else if(cur.left!=null && cur.right!=null){
//            TreeNode targetParent = cur;
//            TreeNode target = cur.right;
//            while(target.left!=null){
//                targetParent = target;
//                target = target.left;
//            }
//            cur.val = target.val;
//            if(target==targetParent.left){
//                targetParent.left = target.right;
//            }else{
//                targetParent.right = target.right;
//            }
//        }
//    }
}
